A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. Many types of computer networks are available, with the types ranging from Local Area Networks (LANs) to Wide Area Networks (WANs). The nodes typically communicate by exchanging discrete frames or packets of data according to pre-defined protocols.
Computer networks may be further interconnected by an intermediate node, known as a router, to extend the effective “size” of each network. Since management of a large system of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as autonomous systems (AS) or routing domains. The networks within a routing domain are typically coupled together by conventional “intradomain” routers. Yet it still may be desirable to increase the number of nodes capable of exchanging data. In this case, “inter-domain” routers executing inter-domain routing protocols are used to interconnect nodes of the various AS.
An example of an inter-domain routing protocol is the Border Gateway Protocol (BGP), which performs routing between AS by exchanging routing and reachability information among inter-domain routers of a network. Specifically, each BGP router maintains a routing table that lists all feasible paths to a particular network. Periodic refreshing of the routing table is generally not performed however, BGP peer routers residing in the autonomous systems exchange routing information under certain circumstances. For example, when a BGP router initially connects to the network, the peer routers exchange the entire contents of their routing tables. Each BGP speaker learns from its peers a set of routes for a prefix, with each of its peers contributing at most one route to this set. Each route has a set of attributes associated with it. The selection of the most preferred route to a destination (address prefix) often involves comparing these attributes.
BGP4 is the de facto standard for inter-domain routing in the Internet. However, BGP4 and other BGP protocols have been shown to experience the problem of long convergence times that often occur when some events, such as topological changes, trigger routing updates. During these long convergence times, the speakers tend to incur more update messages than may be necessary for achieving convergence.